package com.dexter.year2023.charpter2_reverselinklist.level2.topic2_4链表加法;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import java.util.Stack;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 445. 两数相加 II
 * https://leetcode.cn/problems/add-two-numbers-ii/
 * <p>
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个结点只存储一位数字。将这两数相加会返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * <p>
 * 示例1：
 * 输入：l1 = [7,2,4,3], l2 = [5,6,4]
 * 输出：[7,8,0,7]
 * 示例2：
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[8,0,7]
 * 示例3：
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 * <p>
 * 提示：
 * 链表的长度范围为 [1, 100]
 * 0 <= node.val <= 9
 * 输入数据保证链表代表的数字无前导 0
 * <p>
 * 进阶：如果输入链表不能翻转该如何解决？
 *
 * @author Dexter
 */
public class AddTwoNumbers {
    public static void main(String[] args) {
        int[] a = {7, 2, 4, 3};
        Node l1 = initLinkedList(a);
        int[] b = {5, 6, 4};
        Node l2 = initLinkedList(b);
        int testMethod = 1;
        Node newHead = null;
        switch (testMethod) {
            case 1:
                // 法1：用Stack（进阶）
                newHead = addTwoNumbersByStack(l1, l2);
                break;
            case 2:
                // 法2：三次反转链表
                newHead = addTwoNumbersByReverse(l1, l2);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        printLinkedList(newHead);
    }

    public static Node addTwoNumbersByStack(Node head1, Node head2) {
        // 入栈
        Stack<Node> st1 = new Stack<>();
        Stack<Node> st2 = new Stack<>();
        while (head1 != null) {
            st1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            st2.push(head2);
            head2 = head2.next;
        }
        // 进位
        int carry = 0;
        // 新的链表
        Node dummy = new Node(-1);
        // 出栈
        while (!st1.empty() || !st2.empty() || carry > 0) {
            // 定义a\b，参与计算
            Node a = new Node(0);
            Node b = new Node(0);
            if (!st1.empty()) {
                a = st1.pop();
            }
            if (!st2.empty()) {
                b = st2.pop();
            }
            int sum = a.val + b.val + carry;
            carry = sum / 10;
            sum = sum % 10;
            Node cur = new Node(sum);
            // 反转链表
            cur.next = dummy.next;
            dummy.next = cur;
        }
        return dummy.next;
    }

    public static Node addTwoNumbersByReverse(Node head1, Node head2) {
        // 第一轮反转，两次
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        // 遍历，处理相加
        Node dummy = new Node(-1);
        // 移动变量
        Node cur = dummy;
        int carry = 0;
        while (head1 != null || head2 != null) {
            int sum = carry;
            if (head1 != null) {
                sum += head1.val;
                head1 = head1.next;
            }
            if (head2 != null) {
                sum += head2.val;
                head2 = head2.next;
            }
            cur.next = new Node(sum % 10);
            // 移动要饭盆
            cur = cur.next;
            carry = sum / 10;
        }
        // 处理最高级的进位
        if (carry > 0) {
            cur.next = new Node(carry);
        }
        // 第二轮反转，一次
        return reverseList(dummy.next);
    }

    private static Node reverseList(Node head) {
        Node cur = head;
        Node pre = null;
        while (cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
